package basic.sort.greedy;

import java.util.HashSet;

/**
 * @author distantstar
 * @version 1.0
 * @date 2021
 * @description basic.sort.greedy
 * @since JDK1.8
 *
 * 给定一个字符串str，只由‘X’和‘.’两种字符构成。
 * ‘X’表示墙，不能放灯，也不需要点亮
 * ‘.’表示居民点，可以放灯，需要点亮
 * 如果灯放在i位置，可以让i-1，i和i+1三个位置被点亮
 * 返回如果点亮str中所有需要点亮的位置，至少需要几盏灯
 */
public class Lights {

    private static int greedy(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }

        // 转换成字符数组
        char[] chars = str.toCharArray();
        // 灯数
        int light = 0;
        // 字符数组索引
        int index = 0;
        // 循环点灯
        /*
            分两种大情况:
                1 此位置为'X'，则index+1
                2 此位置为'.'，则分小情况：
                    2.1 index+1处为'X'，则此时light++，跳转到index+2；
                    2.2 index+1处为'.'，则可知，无论index+2处为'X'，还是'.'，此处一定要有灯，
                        跳转到index+3
        */
        while (index < chars.length) {
            if (chars[index] == 'X') {
                index++;
            } else {
                // 灯数直接++，缘由可通过上述情况可知
                light++;
                if (chars[index + 1] == 'X') {
                    index += 2;
                } else {
                    index += 3;
                }
            }
        }

        return light;
    }

    public static int minLight1(String road) {
        if (road == null || road.length() == 0) {
            return 0;
        }
        return process(road.toCharArray(), 0, new HashSet<>());
    }

    // str[index....]位置，自由选择放灯还是不放灯
    // str[0..index-1]位置呢？已经做完决定了，那些放了灯的位置，存在lights里
    // 要求选出能照亮所有.的方案，并且在这些有效的方案中，返回最少需要几个灯
    public static int process(char[] str, int index, HashSet<Integer> lights) {
        if (index == str.length) { // 结束的时候
            for (int i = 0; i < str.length; i++) {
                if (str[i] != 'X') { // 当前位置是点的话
                    if (!lights.contains(i - 1) && !lights.contains(i) && !lights.contains(i + 1)) {
                        return Integer.MAX_VALUE;
                    }
                }
            }
            return lights.size();
        } else { // str还没结束
            // i X .
            int no = process(str, index + 1, lights);
            int yes = Integer.MAX_VALUE;
            if (str[index] == '.') {
                lights.add(index);
                yes = process(str, index + 1, lights);
                lights.remove(index);
            }
            return Math.min(no, yes);
        }
    }

    // for test
    public static String randomString(int len) {
        char[] res = new char[(int) (Math.random() * len) + 1];
        for (int i = 0; i < res.length; i++) {
            res[i] = Math.random() < 0.5 ? 'X' : '.';
        }
        return String.valueOf(res);
    }

    public static void main(String[] args) {
        int len = 20;
        int testTime = 100000;
        for (int i = 0; i < testTime; i++) {
            String test = randomString(len);
            int ans1 = minLight1(test);
            int ans2 = greedy(test);
            if (ans1 != ans2) {
                System.out.println("oops!");
            }
        }
        System.out.println("finish!");
    }
}
